#include <iostream>
#include <vector>

static constexpr const char _end = '\0';
static constexpr const char _all = '.';
static constexpr const char _any = '*';

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        /*!
            \param s Text string
            \param p Pattern string

            Use \c p1 and \c p2 pointing to the current char of \c s and \c p and move forward
            them if current chars match.
        */

        return isMatchImpl(s.data(), p.data());
    }

    bool isMatchImpl(const char *s, const char *p) {
        const char *p1 = s;
        const char *p2 = p;

        while (*p2 != _end) {
            if (*(p2 + 1) == _any) {
                const char &repeated = *p2;
                p2 += 2;

                // Ignore the wild card first
                if (isMatchImpl(p1, p2))
                    return true;

                // Test incoming repeated chars
                if (repeated == _all) {
                    while (*p1 != _end) {
                        if (isMatchImpl(++p1, p2))
                            return true;
                    }
                } else {
                    while (*p1 == repeated) {
                        if (isMatchImpl(++p1, p2))
                            return true;
                    }
                }

                continue;
            }

            if (*p1 == _end)
                break;

            if (*p1 == *p2 || *p2 == _all) {
                p1++;
                p2++;
                continue;
            }

            return false;
        }

        return *p1 == _end && *p2 == _end;
    }
};

int main(int argc, char *argv[]) {
    std::cout << Solution().isMatch("bccbbabcaccacbcacaa", ".*b.*c*.*.*.c*a*.c") << std::endl;
    return 0;
}